home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ddj0897.zip / AA897.ZIP / DRIVER.CPP next >
C/C++ Source or Header  |  1997-04-30  |  7KB  |  196 lines
  1. // Driver program for cycle-less version of topological sorting
  2.  
  3. ////////////////////////////////////////////////////////////////////
  4. //
  5. // Include files
  6.  
  7. #include "topsort.h"
  8.  
  9. // for now, the mmbers are strings
  10. #include <string>
  11. #include <iostream>
  12.  
  13. typedef pair< char **, char ** > Relation;
  14.  
  15. typedef vector< string, allocator < string > > stringVector;
  16. // typedef pair< stringVector::iterator, stringVector::iterator > stringRelation;
  17. typedef pair< string *, string * > stringRelation;
  18. typedef vector< stringRelation, allocator < stringRelation > > stringRelations;
  19.  
  20. void exampleWithArrays()
  21. {
  22.     char *names[8] = {"A", "B", "C", "D", "E", "F", "G", "H" };
  23.     char *results[8];
  24.     Relation rels[20];
  25.     int numSorted;
  26.     int numCycles;
  27.     int i;
  28.     int numRels = 0;
  29.     Cycle theCycles[20];
  30.  
  31.     cout << "Example 1: B, A, C, D" << endl;
  32.  
  33.     // b precedes a
  34.     rels[numRels++] = make_pair(&names[1], &names[0]);
  35.     // b precedes d
  36.     rels[numRels++] = make_pair(&names[1], &names[3]);
  37.     // a precedes c
  38.     rels[numRels++] = make_pair(&names[0], &names[2]);
  39.     // c precedes d
  40.     rels[numRels++] = make_pair(&names[2], &names[3]);
  41.     numSorted = topsort(names, names + 4, rels, rels + numRels, results);
  42.  
  43.     // print out the results.  The order should be B, A, C, D
  44.     if (numSorted != 4)
  45.         cout << "topsort reports there is a cycle " << endl;
  46.     else
  47.         cout << "topsort reports there is no cycle" << endl;
  48.     for (i = 0; i < numSorted; i++)
  49.         cout << results[i] << endl;
  50.  
  51.     
  52.     numCycles = cycles(names, names + 4, rels, rels + numRels, theCycles);
  53.     if (numCycles == 0)
  54.         cout << "cycles reports (correctly) that there is no cycle" << endl;
  55.     else
  56.         cout << "cycles reports (incorrectly) that there is a cycle" << endl;
  57.  
  58.     cout << "Example 1A: B, A, [C  D]" << endl;
  59.     // add in a recursive call: d precedes c.  Now there is a cycle,
  60.     // between d and c, so the order printed by topsort should be B A
  61.     // c precedes d
  62.     rels[numRels++] = make_pair(&names[3], &names[2]);
  63.     numSorted = topsort(names, names + 4, rels, rels + numRels, results);
  64.  
  65.     // print out the results.  The order should be B, A
  66.     if (numSorted == 2)
  67.         cout << "topsort reports (correctly) that there is a cycle " << endl;
  68.     else if (numSorted == 4)
  69.         cout << "topsort reports (incorrectly) that there is no cycle " << endl;
  70.     else
  71.         cout << "topsort reports (incorrectly) that there is a cycle after " << numSorted << " elements" << endl;
  72.     for (i = 0; i < numSorted; i++)
  73.         cout << results[i] << endl;
  74.  
  75.     numCycles = cycles(names, names + 4, rels, rels + numRels, theCycles);
  76.     if (numCycles == 0)
  77.         cout << "cycles reports (incorrectly) that there is no cycle" << endl;
  78.     else
  79.         cout << "cycles reports (correctly) that there is a cycle" << endl;
  80.     for (i = 0; i < numCycles; i++)
  81.     {
  82.         cout << "cycle " << i << ": ";
  83.         for (int j = 0; j < theCycles[i].size(); j++)
  84.             cout << names[theCycles[i][j]] << " ";
  85.         cout << endl;
  86.     }
  87.  
  88.     bool haveCycle;
  89.     haveCycle = topsortWithCycles(names, names + 4, rels, rels + numRels, results);
  90.  
  91.     // print out the results.  The order should be B, A
  92.     if (haveCycle)
  93.         cout << "topsortWithCycles reports (correctly) that there is a cycle " << endl;
  94.     else 
  95.         cout << "topsortWithCycles reports (incorrectly) that there is no cycle " << endl;
  96.     for (i = 0; i < 4; i++)
  97.         cout << results[i] << endl;
  98. }
  99.  
  100. void exampleWithVectors()
  101. {
  102.     stringVector strings;
  103.     int numSorted;
  104.     int numCycles;
  105.     int i;
  106.  
  107.     cout << "Example 2: A, [B, C  D], E, [F, G]" << endl;
  108.     strings.push_back("a");
  109.     strings.push_back("b");
  110.     strings.push_back("c");
  111.     strings.push_back("d");
  112.     strings.push_back("e");
  113.     strings.push_back("f");
  114.     strings.push_back("g");
  115.  
  116.     stringRelations rels2;
  117.     // A precedes B
  118.     rels2.push_back(make_pair(&strings[0], &strings[1]));
  119.     // B precedes C
  120.     rels2.push_back(make_pair(&strings[1], &strings[2]));
  121.     // C precedes D
  122.     rels2.push_back(make_pair(&strings[2], &strings[3]));
  123.     // C precedes B
  124.     rels2.push_back(make_pair(&strings[2], &strings[1]));
  125.     // D precedes B
  126.     rels2.push_back(make_pair(&strings[3], &strings[1]));
  127.     // D precedes E
  128.     rels2.push_back(make_pair(&strings[3], &strings[4]));
  129.     // D precedes F
  130.     rels2.push_back(make_pair(&strings[3], &strings[5]));
  131.     // F precedes G
  132.     rels2.push_back(make_pair(&strings[5], &strings[6]));
  133.     // G precedes F
  134.     rels2.push_back(make_pair(&strings[6], &strings[5]));
  135.  
  136.     stringVector stringResults(strings.size());
  137.     numSorted = topsort(strings.begin(), 
  138.                         strings.end(), 
  139.                         rels2.begin(), 
  140.                         rels2.begin() + rels2.size(), 
  141.                         stringResults.begin());
  142.     if (numSorted == 1)
  143.         cout << "topsort reports (correctly) that there is a cycle after 1 element" << endl;
  144.     else if (numSorted == strings.size())
  145.         cout << "topsort reports (incorrectly) that there is no cycle " << endl;
  146.     else
  147.         cout << "topsort reports (incorrectly) that there is a cycle after " << numSorted << " elements" << endl;
  148.     for (i = 0; i < numSorted; i++)
  149.         cout << stringResults[i] << endl;
  150.  
  151.     vector < Cycle, allocator < Cycle > > cycleResults(strings.size());
  152.     numCycles = cycles(strings.begin(), 
  153.                        strings.end(), 
  154.                        rels2.begin(), 
  155.                        rels2.begin() + rels2.size(), 
  156.                        cycleResults.begin());
  157.     if (numCycles == 2)
  158.         cout << "cycles reports (correctly) that there are two cycles" << endl;
  159.     else if (numCycles == 0)
  160.         cout << "cycles reports (incorrectly) that there is no cycle" << endl;
  161.     else
  162.         cout << "cycles reports (incorrectly) that there are " << numCycles << " cycles" << endl;
  163.     for (i = 0; i < numCycles; i++)
  164.     {
  165.         cout << "cycle " << i << ": ";
  166.         for (int j = 0; j < cycleResults[i].size(); j++)
  167.             cout << strings[cycleResults[i][j]] << " ";
  168.         cout << endl;
  169.     }
  170.  
  171.     bool haveCycle;
  172.     haveCycle = topsortWithCycles(strings.begin(), 
  173.                         strings.end(), 
  174.                         rels2.begin(), 
  175.                         rels2.begin() + rels2.size(), 
  176.                         stringResults.begin());
  177.  
  178.     // print out the results.  The order should be A [B C D] E [F G] or 
  179.     //                                             A [B C D] [F G] E
  180.     // where the bracketed members can occur in any order
  181.  
  182.     if (haveCycle)
  183.         cout << "topsortWithCycles reports (correctly) that there is a cycle " << endl;
  184.     else 
  185.         cout << "topsortWithCycles reports (incorrectly) that there is no cycle " << endl;
  186.     for (i = 0; i < strings.size(); i++)
  187.         cout << stringResults[i] << endl;
  188. }
  189.  
  190. int main(int argc, char **argv)
  191. {
  192.     exampleWithArrays();
  193.     exampleWithVectors();
  194.     return 0;
  195. }
  196.